/*
 * scutable.c
 * O(1) table
 *
 * Q: WHAT DOES THIS ALL MEAN? SLICES? WTF?
 * A: Calm down. Here, take this pill.
 * First of all, you don't need to use slices at all, because the
 * default slice (occupied/not occupied) is used internally.
 * Second, it's really very simple; since slices are not exposed, you
 * only need to know tbladdslice and tblswitchslice. tbladdslice is
 * trivial, and tblswitchslice is self-explaining: it switches a
 * table entry between being in the slice and not being in the slice.
 *
 * Q: So, what do slices actually do?
 * A: Glad to see the pill worked.
 * A slice partitions the table entries in two sets: those in the slice and
 * those not in the slice. It does this in a way that makes it O(1) to
 * switch membership, as well as O(1) to find all members or non-members of
 * the slice. This makes it efficient to iterate over a certain subset of
 * table entries.
 * The easiest example is iterating over all occupied entries (the OCCUPIED
 * slice is the default slice that you never see). But it can be used, for
 * example, to iterate over all mapped processes without having to define
 * a new table for them.
 *
 * Q: Hey! That's not difficult after all!
 * A: You're welcome.
 *
 * A: This gives us a datastructure that is
 * O(1) insert (at a specific index, or a random one)
 * O(1) delete
 * O(1) find next (iteration)
 * O(1) get by index (and, with tblfindhash, O(~1) get by property)
 * Q: But I didn't ask anything!
 */

#define _XOPEN_SOURCE 500

#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include "scutable.h"

#undef LOCK
#undef UNLOCK
#undef UNLOCKRETI
#undef UNLOCKRETP

#ifdef SCU_TABLE_LOCKING
#define LOCK(tbl)               scos_mutex_lock(&tbl->lock)
#define UNLOCK(tbl)             scos_mutex_unlock(&tbl->lock)
#define UNLOCKRETI(tbl, retval) { int _retval = retval; UNLOCK(tbl); return _retval; }
#define UNLOCKRETP(tbl, retval) { void *_retval = retval; UNLOCK(tbl); return _retval; }
#else
#define LOCK(tbl)
#define UNLOCK(tbl)
#define UNLOCKRETI(tbl, retval) { return retval; }
#define UNLOCKRETP(tbl, retval) { return retval; }
#endif /* SCU_TABLE_LOCKING */

#define MAX(a, b) (((a)>(b))?(a):(b))

#define NONMEMBER SCU_TABLE_NONMEMBER
#define MEMBER    SCU_TABLE_MEMBER
#define OCCUPIED  SCU_TABLE_SLICE_OCCUPIED

int slcresize(slice_t *slc, int length)
{
  int i;
  slice_item_t *newdata;

  if (!slc)
    return -EINVAL;
    
  //printf("resizing slice %p: %d -> %d\n", slc, slc->length, length);

  if (length <= slc->length)
    return 0;

  if (!(newdata = (slice_item_t*) realloc(slc->data, length*sizeof(slice_item_t))))
    return -ENOMEM;

  slc->data = newdata;
 
  for (i=slc->length; i < length; i++)
  {
    slc->data[i].member = 0;
    slc->data[i].previous = i-1;
    slc->data[i].next = i+1;
  }

  if (slc->first[NONMEMBER] == -1)
  {
    slc->data[slc->length].previous = -1;
    slc->first[NONMEMBER] = slc->length;
  }
  else /* slc->last[NONMEMBER] != -1 */
  {
    slc->data[slc->length].previous = slc->last[NONMEMBER];
    slc->data[slc->last[NONMEMBER]].next = slc->length;
  }  

  slc->data[length-1].next = -1;
  slc->last[NONMEMBER] = length-1;
  slc->length = length;

  return 0;
}

int slccreate(slice_t *slc, int length)
{
  if (!slc)
    return -EINVAL;
    
  //printf("creating slice %p: %d\n", slc, length);

  if (length <= 0)
    return -EINVAL;

  slc->length = slc->members = 0;
  slc->data = NULL;
  slc->first[MEMBER] = slc->last[MEMBER] =
    slc->first[NONMEMBER] = slc->last[NONMEMBER] = -1;

  return slcresize(slc, length);    
}

int slcdestroy(slice_t *slc)
{
  if (!slc)
    return -EINVAL;

  //printf("destroying slice %p\n", slc);

  free(slc->data);
  
  slc->data = NULL;
  slc->length = slc->members = 0;
  slc->first[MEMBER] = slc->last[MEMBER] =
    slc->first[NONMEMBER] = slc->last[NONMEMBER] = -1;  

  return 0;
}

int slcgetnext(slice_t *slc, int i, int member)
{
  int retval;

  if (!slc)
    return -EINVAL;

  if (i < 0 || i >= slc->length)
    retval = slc->first[member];
  else
  {
    if (slc->data[i].member != member)
      retval = -EINVAL;
    else
      retval = slc->data[i].next;
  }

  //printf("getting next element for %p at %d (%d) -> %d\n", slc, i, member, retval);

  return retval;
}

int slcswitch(slice_t *slc, int i, int member)
{
  int previous;

  if (!slc)
    return -EINVAL;

  //printf("switching element %d for slice %p: %d -> %d\n", i, slc,
//         slc->data[i].member, member);

  if (i < 0 || i >= slc->length)
    return -EINVAL;

  if (slc->data[i].member == member)
    return 0;

  previous = slc->data[i].previous;

  if (i == slc->first[!member])
    slc->first[!member] = slc->data[i].next;
  else
    slc->data[slc->data[i].previous].next = slc->data[i].next;

  if (i == slc->last[!member])
    slc->last[!member] = slc->data[i].previous;
  else
    slc->data[slc->data[i].next].previous = slc->data[i].previous;

  if (slc->last[member] == -1)
  {
    slc->first[member] = i;
    slc->data[i].previous = -1;
  }
  else
  {
    slc->data[slc->last[member]].next = i;
    slc->data[i].previous = slc->last[member];
  }

  slc->last[member] = i;
  slc->data[i].next = -1;
  slc->data[i].member = member;

  if (member == MEMBER)
    slc->members++;
  else
    slc->members--;

  if (previous == -1)
    return slc->length;
  else
    return previous;
}

int tbladdslice(table_t *tbl, int slice)
{
  int s, retval;
  slice_t *newdata;

  if (!tbl)
    return -EINVAL;

  if (slice < 0)
    return -EINVAL;

  if (!(newdata = (slice_t*) realloc(tbl->slice,
                                     MAX(tbl->slices, slice+1)*
                                     sizeof(slice_t))))
    return -ENOMEM;

  for (s=tbl->slices; s < MAX(tbl->slices, slice+1); s++)
  { 
    if ((retval = slccreate(&newdata[s], tbl->length)))
    {
      for (; s >= tbl->slices; s--)
        slcdestroy(&newdata[s]);
      free(newdata);
    
      return retval;
    }
  }
  
  tbl->slice = newdata;
  tbl->slices = MAX(tbl->slices, slice+1);
 
  return 0;
}

int tblsortslice(table_t *tbl, int slice)
{
  int i, retval;
  slice_t tempslice;

  if (!tbl)
    return -EINVAL;

  if (slice < 0)
    return -EINVAL;

  if ((retval = slccreate(&tempslice, tbl->length)))
    return retval;

  for (i=0; i < tbl->length; i++)
  {
    if (tbl->slice[slice].data[i].member == MEMBER)
    {
      if ((retval = slcswitch(&tempslice, i, MEMBER)) < 0)
      {
	slcdestroy(&tempslice);
	return retval;
      }
    }
  } 

  if ((retval = slcdestroy(&tbl->slice[slice])))
  {
    slcdestroy(&tempslice);
    return retval;
  }

  tbl->slice[slice] = tempslice;

  return 0;
}

int tblcreate(table_t *tbl, int size)
{
  int retval;

  if (!tbl)
    return -EINVAL;

  if (size <= 0)
    return -EINVAL;

  tbl->size = size;
  tbl->length = 1;
  tbl->slice = NULL;
  tbl->slices = 0;
  tbl->hashlength = 0;
  tbl->hash = NULL;
  
  if (!(tbl->data = (void**) calloc(tbl->length, sizeof(void*))))
    return -ENOMEM;

  if ((retval = tbladdslice(tbl, OCCUPIED)))
  {
    free(tbl->data);
    return retval;
  }

#ifdef SCU_TABLE_LOCKING
  scos_mutex_init(&tbl->lock);
#endif

  return 0;
}

int tbldestroy(table_t *tbl, int dofree)
{
  int i=-1;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data)
    UNLOCKRETI(tbl, -EINVAL);

  while ((i = tblgetnexti(tbl, i)) >= 0)
    i = tbldel(tbl, i, dofree);

  free(tbl->data);
  slcdestroy(&tbl->slice[0]);
  
  tbl->data = NULL;
  tbl->size = tbl->length = 0;

  UNLOCK(tbl);
#ifdef SCU_TABLE_LOCKING
  scos_mutex_destroy(&tbl->lock);
#endif  

  return 0;
}

int tblclear(table_t *tbl, int dofree)
{
  int i=-1;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data)
    UNLOCKRETI(tbl, -EINVAL);

  while ((i = tblgetnexti(tbl, i)) >= 0)
    i = tbldel(tbl, i, dofree);

  UNLOCKRETI(tbl, 0);
}

int _tbladd(table_t *tbl, void *data)
{
  int i;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data || !data)
    UNLOCKRETI(tbl, -EINVAL);

  if (tbl->slice[OCCUPIED].members == tbl->length)
    i = tbl->length;
  else
    i = slcgetnext(&tbl->slice[OCCUPIED], -1, NONMEMBER);

  UNLOCKRETI(tbl, _tbladdi(tbl, data, i));
}

int _tbladdi(table_t *tbl, void *data, int i)
{
  int ii, retval, s;
  void **newdata;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data || !data || i < 0)
    UNLOCKRETI(tbl, -EINVAL);

  while (i >= tbl->length)
  {
    if (!(newdata = (void**) realloc(tbl->data, tbl->length*2*sizeof(void*))))
      UNLOCKRETI(tbl, -ENOMEM);
  
    for (s=0; s < tbl->slices; s++)
      if ((retval = slcresize(&tbl->slice[s], tbl->length*2)))
      {
        free(newdata);
        UNLOCKRETI(tbl, retval);
      }

    tbl->data = newdata;
    tbl->length = tbl->length * 2;

    for (ii=tbl->length/2; ii < tbl->length; ii++)
      tbl->data[ii] = NULL;
  }  

  if (tbl->data[i])
    UNLOCKRETI(tbl, -EEXIST);

  tbl->data[i] = data;

  if ((retval = slcswitch(&tbl->slice[OCCUPIED], i, MEMBER)) < 0)
    UNLOCKRETI(tbl, retval);

  UNLOCKRETI(tbl, i);
}

int _tbladdnew(table_t *tbl, void **data)
{
  int retval;
  void *newdata;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (!(newdata = calloc(1, tbl->size)))
    UNLOCKRETI(tbl, -ENOMEM);

  if ((retval = _tbladd(tbl, newdata)) < 0)
    free(newdata);

  if (data)
    *data = newdata;

  UNLOCKRETI(tbl, retval);
}

int _tbladdnewi(table_t *tbl, void **data, int i)
{
  int retval;
  void *newdata;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (!(newdata = calloc(1, tbl->size)))
    UNLOCKRETI(tbl, -ENOMEM);

  if ((retval = _tbladdi(tbl, newdata, i)) < 0)
    free(newdata);

  if (data)
    *data = newdata;  

  UNLOCKRETI(tbl, retval);
}

int tbldel(table_t *tbl, int i, int dofree)
{
  int s;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data || i < 0 || i >= tbl->length || !tbl->data[i])
    UNLOCKRETI(tbl, -EINVAL);

  if (dofree)
    free(tbl->data[i]);

  tbl->data[i] = NULL;

  for (s=1; s < tbl->slices; s++)
    slcswitch(&tbl->slice[s], i, NONMEMBER);

  i = slcswitch(&tbl->slice[OCCUPIED], i, NONMEMBER);

  UNLOCKRETI(tbl, i);
}

void *_tblget(table_t *tbl, int i, void** data)
{
  if (data)
    *data = NULL;

  if (!tbl)
    return NULL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data || i < 0 || i >= tbl->length)
    UNLOCKRETP(tbl, NULL);

  if (data)
    *data = tbl->data[i];

  UNLOCKRETP(tbl, tbl->data[i]);
}

int tblgetslicenexti(table_t *tbl, int slice, int i)
{
  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data || slice < 0 || slice >= tbl->slices)
    UNLOCKRETI(tbl, -EINVAL);

  i = slcgetnext(&tbl->slice[slice], i, MEMBER);

  if (i < 0 || i >= tbl->length)
    UNLOCKRETI(tbl, -ENOENT);

  UNLOCKRETI(tbl, i);
}

int tblgetnexti(table_t *tbl, int i)
{
  return tblgetslicenexti(tbl, 0, i);
}

void *_tblgetnextelement(table_t *tbl, int *i, void **data)
{
  if (data)
    *data = NULL;

  if (!tbl)
    return NULL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data)
    UNLOCKRETP(tbl, NULL);

  *i = slcgetnext(&tbl->slice[OCCUPIED], *i, MEMBER);

  if (*i < 0 || *i >= tbl->length)
  {
    *i = -ENOENT;
    UNLOCKRETP(tbl, NULL);
  }

  if (data)
    *data = tbl->data[*i];

  UNLOCKRETP(tbl, tbl->data[*i]);
}

int tblgetelements(table_t *tbl)
{
  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  UNLOCKRETI(tbl, tbl->slice[OCCUPIED].members);
}

int tblswitchslice(table_t *tbl, int slice, int i, int member)
{
  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data ||
      i < 0 || i >= tbl->length || slice < 0 || slice >= tbl->slices)
    UNLOCKRETI(tbl, -EINVAL);

  UNLOCKRETI(tbl, slcswitch(&tbl->slice[slice], i, member));
}

int tblcreatehash(table_t *tbl, int size, int length)
{
  if (!tbl)
    return -EINVAL;

  LOCK(tbl);
  
  if (length <= 0)
    UNLOCKRETI(tbl, -EINVAL);

  tbl->hashlength = length;
  tbl->hashsize = size;

  if (!(tbl->hash = (table_hash_t**) calloc(tbl->hashlength, sizeof(table_hash_t*))))
    UNLOCKRETI(tbl, -ENOMEM); 
  
  UNLOCKRETI(tbl, 0);
}

int _tbldohash(table_t *tbl, void *data)
{
  int i, hash;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);  

  if (tbl->hashlength <= 0 || tbl->hashsize <= 0 || !data)
    UNLOCKRETI(tbl, -EINVAL);

  for (i=0, hash = 0; i < tbl->hashsize; i++)
    hash = (hash + *((unsigned char*)data+i)) % tbl->hashlength;

  UNLOCKRETI(tbl, hash);
}

int tbladdhash(table_t *tbl, void *data, int i)
{
  int hash;
  table_hash_t *h;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->hashlength <=0 || tbl->hashsize <= 0 || !tbl->hash || !data)
    UNLOCKRETI(tbl, -EINVAL);

  if ((hash = _tbldohash(tbl, data)) < 0)
    UNLOCKRETI(tbl, hash);

  if (!(h = tbl->hash[hash]))
  {
    if (!(h = tbl->hash[hash] = (table_hash_t*) malloc(sizeof(table_hash_t))))
      	UNLOCKRETI(tbl, -ENOMEM);
  }
  else
  {
    while (h->next)
      h = h->next;
    
     if (!(h->next = (table_hash_t*) malloc(sizeof(table_hash_t))))
	UNLOCKRETI(tbl, -ENOMEM);
     h = h->next;
  }

  if (!(h->data = malloc(tbl->hashsize)))
    UNLOCKRETI(tbl, -ENOMEM);
  
  memcpy(h->data, data, tbl->hashsize);
  h->i = i;
  h->next = NULL;

//printf("tbladdhash: %p -> %d\n", *((int*)h->data), h->i);

  UNLOCKRETI(tbl, 0);
}

int tblfindhash(table_t *tbl, void *data)
{
  int hash;
  table_hash_t *h;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->hashlength <=0 || tbl->hashsize <= 0 || !tbl->hash || !data)
    UNLOCKRETI(tbl, -EINVAL);

  if ((hash =  _tbldohash(tbl, data)) < 0)
    UNLOCKRETI(tbl, hash);

  h = tbl->hash[hash];
  while (h && memcmp(h->data, data, tbl->hashsize))
    h = h->next;

  if (!h)
    UNLOCKRETI(tbl, -ENOENT);
  
//printf("tblfindhash: %p -> %d\n", *((int*)h->data), h->i);

  UNLOCKRETI(tbl, h->i);
}

int tbldelhash(table_t *tbl, void *data)
{
  int hash;
  table_hash_t *h, *p;

  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->hashlength <=0 || tbl->hashsize <= 0 || !tbl->hash || !data)
    UNLOCKRETI(tbl, -EINVAL);

  if ((hash = _tbldohash(tbl, data)) < 0)
    UNLOCKRETI(tbl, hash);

  p = NULL;
  h = tbl->hash[hash];
  while (h && memcmp(h->data, data, tbl->hashsize))
  {
    p = h;
    h = h->next;
  }

  if (!h)
    UNLOCKRETI(tbl, -ENOENT);

  if (!p)
    tbl->hash[hash] = h->next;
  else
    p->next = h->next;

  free(h->data);
  free(h);
  
  UNLOCKRETI(tbl, 0);
}

int tbldestroyhash(table_t *tbl)
{
  int i;
  table_hash_t *h, *temp;
  
  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->hashlength <=0 || !tbl->hash)
    UNLOCKRETI(tbl, -EINVAL);

  for (i=0; i < tbl->hashlength; i++)
  {
    h = tbl->hash[i];
    while (h)
    {
      temp = h;
      h = h->next;
      
      free(temp->data);
      free(temp);
    }
  }

  free(tbl->hash);
  tbl->hash = NULL;  

  UNLOCKRETI(tbl, 0);
}

int tblsort(table_t *tbl, int(*compar)(const void*, const void*))
{
  if (!tbl)
    return -EINVAL;

  LOCK(tbl);

  if (tbl->length <= 0 || tbl->size <= 0 || !tbl->data)
    UNLOCKRETI(tbl, -EINVAL);

  /* NOTE: DOES NOT RENUMBER HASHES */
  /* NOTE: OR SLICES, FOR THAT MATTER */
  qsort(tbl->data, tbl->length, sizeof(void*), compar);

  UNLOCKRETI(tbl, 0);
}

int tblcopy(table_t *dst, table_t *src, int dofree)
{
  int id=-1, retval;
  void *item;

  if (!src || !dst)
    return -EINVAL;

  LOCK(src);
  LOCK(dst);

  retval = tblclear(dst, dofree);
  if (retval < 0)
  {
    UNLOCK(dst);
    UNLOCK(src);
    return retval;
  }
  
  while (tblget(src, id = tblgetnexti(src, id), &item))
  {
    retval = _tbladdi(dst, item, id);
    if (retval < 0)
    {
      UNLOCK(dst);
      UNLOCK(src);
      return retval;
    }
  }

  UNLOCK(dst);
  UNLOCK(src);
  return 0;
}
